package com.leetcode.no42;


import java.util.Arrays;
import java.util.Stack;


// 单调递减栈
//
//理解题目，参考图解，注意题目的性质，当后面的柱子高度比前面的低时，是无法接雨水的
//当找到一根比前面高的柱子，就可以计算接到的雨水
//所以使用单调递减栈
//对更低的柱子入栈
//
//更低的柱子以为这后面如果能找到高柱子，这里就能接到雨水，所以入栈把它保存起来
//平地相当于高度 0 的柱子，没有什么特别影响
//当出现高于栈顶的柱子时
//41. 说明可以对前面的柱子结算了
//42. 计算已经到手的雨水，然后出栈前面更低的柱子
//
//计算雨水的时候需要注意的是
//
//雨水区域的右边 r 指的自然是当前索引 i
//底部是栈顶 st.top() ，因为遇到了更高的右边，所以它即将出栈，使用 cur 来记录它，并让它出栈
//左边 l 就是新的栈顶 st.top()
//雨水的区域全部确定了，水坑的高度就是左右两边更低的一边减去底部，宽度是在左右中间
//使用乘法即可计算面积

// height = [0,1,0,2,1,0,1,3,2,1,2,1]
public class Solution {
    public int trap(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int left = 0, right = height.length - 1;
        int leftEnd = height[left], rightEnd = height[right];
        int sum = 0;

        // 对于每一个i 找左右两边最大值 然后用min(最最大值，最小值)-height[i]
        while (left < right) {
            // 总是移动较短的柱子
            if (leftEnd < rightEnd) {
                left++;
                if (height[left] < leftEnd) {
                    // 如果新柱子比左端短，累加柱子差
                    sum += leftEnd - height[left];
                } else {
                    // 新柱子比左端高，设新柱子为左端
                    leftEnd = height[left];
                }
            } else {
                right--;
                if (height[right] < rightEnd) {
                    // 如果新柱子比右端短，累加柱子差
                } else {
                    // 新柱子比右端高，短设新柱子为右端
                    rightEnd = height[right];
                }
            }
        }
        return sum;
    }

    public int trap01(int[] height) {
        if (height.length < 3) {
            return 0;
        }

        int[] ansRight = new int[height.length];
        int[] ansLeft = new int[height.length];
        int res = 0;

        // 找到左边下一个更大值的一个单调栈
        Stack<Integer> stack = new Stack<>();
        for (int i = height.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                stack.pop();
            }
            ansRight[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // 找到左边下一个更大值
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                stack.pop();
            }
            ansLeft[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }


        for (int i = 1; i < ansLeft.length - 1; i++) {

            if (ansLeft[i] != -1 && ansRight[i] != -1) {
                res += (ansRight[i] - 1 - ansLeft[i]) * (Math.min(ansLeft[i], ansRight[i]) - height[i]);
            }

//            if (ansLeft[i] == -1 && ansRight[i] != -1) {
//                res += ansRight[i] - 1 - i;
//            }
//
//            if (ansRight[i] == -1 && ansLeft[i] != -1) {
//                res += i - 1 - ansLeft[i];
//            }
        }

        System.out.println(Arrays.toString(ansLeft));
        System.out.println(Arrays.toString(ansRight));
        System.out.println(res);
        return 0;
    }

    public int trap02(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int top = stack.pop();
                if (stack.isEmpty())
                    break;
                int distance = i - stack.peek() - 1;
                int bounded_height = Math.min(height[i], height[stack.peek()]) - height[top];
                res += distance * bounded_height;
            }
            stack.push(i);
        }
        System.out.println(res);
        return res;
    }

    public int trap03(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        int ans = 0;
        int size = height.length;
        int[] left_max = new int[size];
        int[] right_max = new int[size];
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }
        System.out.println(Arrays.toString(height));
        System.out.println(Arrays.toString(left_max));
        System.out.println(Arrays.toString(right_max));
        return ans;

    }

    public int trap04(int[] height) {
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int ans = 0;

        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int curIndex = stack.pop();

                // 如果栈顶元素一直相等，那么全都pop出去，只留第一个。
                while (!stack.isEmpty() && height[stack.peek()] == height[curIndex]) {
                    stack.pop();
                }

                if (!stack.isEmpty()) {
                    int stackTop = stack.peek();
                    // stackTop此时指向的是此次接住的雨水的左边界的位置。右边界是当前的柱体，即i。
                    // Math.min(height[stackTop], height[i]) 是左右柱子高度的min，减去height[curIdx]就是雨水的高度。
                    // i - stackTop - 1 是雨水的宽度。
                    ans += (Math.min(height[stackTop], height[i]) - height[curIndex]) * (i - stackTop - 1);
                }
            }
            stack.push(i);
        }
        return ans;
    }

    // main
    public static void main(String[] args) {
        Solution s1 = new Solution();
//        s1.trap02(new int[]{6, 5, 4, 3, 2, 1, 0, 7});
//        s1.trap02(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
//        s1.trap02(new int[]{4, 2, 0, 3, 2, 5});
        s1.trap03(new int[]{6, 5, 4, 3, 2, 1, 0, 7});
        s1.trap03(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        s1.trap03(new int[]{4, 2, 0, 3, 2, 5});
    }

}
